package leetcode.problems;

import org.junit.Test;

/**
 * Created by gmwang on 2018/7/25
 * 岛屿周界
 */
public class _0813IslandPerimeter {
    /**
     * You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water.
     * 你得到的地图是一个二维整数网格，其中1代表陆地，0代表水。
     * <p>
     * Grid cells are connected horizontally/vertically (not diagonally).
     * 网格单元水平/垂直（非对角线）连接。
     * <p>
     * The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).
     * 网格完全被水包围，并且正好有一个岛（即，一个或多个连接的陆地单元）。
     * <p>
     * The island doesn't have "lakes" (water inside that isn't connected to the water around the island).
     * 岛上没有“湖泊”（里面的水没有连接到岛上的水）。
     * <p>
     * One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100.
     * 一个单元格是边长为1的正方形。网格为矩形，宽度和高度不超过100。
     * <p>
     * Determine the perimeter of the island.
     * 确定岛的周长。
     * <p>
     * <p>
     * Example:
     * <p>
     * Input:
     * [[0,1,0,0],
     * [1,1,1,0],
     * [0,1,0,0],
     * [1,1,0,0]]
     * <p>
     * Output: 16
     * <p>
     * Explanation: The perimeter is the 16 yellow stripes in the image below:
     * /**
     *
     * @param grid
     * @return
     */
    public int islandPerimeter(int[][] grid) {
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            //针对第一行/列和最后一行/列单独处理
            for (int j = 0; j < grid[i].length; j++) {
                if (i == 0) {
                    if (grid[i][j] == 1) {
                        res += 4 * 1;
                        if (j != 0) {
                            if (grid[i][j - 1] == 1) {
                                res -= 2;
                            }
                        }
                    }
                } else {
                    //one land
                    if (grid[i][j] == 1) {
                        res += 4;
                        if (j != 0) {
                            if (grid[i][j - 1] == 1) {
                                res -= 2;
                            }
                        }
                        if (grid[i - 1][j] == 1) {
                            res -= 2;
                        }
                    }
                }
            }
        }
        return res;
    }
//    public int islandPerimeter(int[][] grid) {
//        int islands = 0, neighbours = 0;
//
//        for (int i = 0; i < grid.length; i++) {
//            for (int j = 0; j < grid[i].length; j++) {
//                if (grid[i][j] == 1) {
//                    islands++; // count islands
//                    if (i < grid.length - 1 && grid[i + 1][j] == 1) neighbours++; // count down neighbours
//                    if (j < grid[i].length - 1 && grid[i][j + 1] == 1) neighbours++; // count right neighbours
//                }
//            }
//        }
//
//        return islands * 4 - neighbours * 2;
//    }
    @Test
    public void test() {
        int[][] ints = {{0, 1, 0, 0}, {1, 1, 1, 0}, {0, 1, 0, 0}, {1, 1, 0, 0}};
        int res = islandPerimeter(ints);
        System.out.println(res);
    }
}
